NO.9 回文数 简单
思路一:字符串法 最简单的解法就是直接将数字转换为字符串s,然后将字符串翻转得到re,最后判断s和rs是否相等,相等则是回文。
1 | public boolean isPalindrome(int x) { |
思路二:翻转一半法 题目要求中有说,不能将整数转化为字符串来解决这个问题。但是依然可以使用字符串法的翻转思路,将数字进行翻转也并不难,例如“1221”,我们需要将后半部分“21”翻转为“12”再和前半部分“12”作比较,相同所以“1221”是回文数。
算法步骤:1.如果数字是负数,那么一定不是回文数。如果数字最后一位是”0“,但数字本身并不是”0“,那么该数字也一定不是回文数。2.如何翻转数字的后半部分:例如“x=1221”,先”1221%10“得到1,然后“x/=10”使x=122, 最后”t=t*10+1”得到t=1;再次“122%10”得到2,然后“x/=10”使x=12,“最后”t=t*10+2”得到t=12。3.将数字后半部分翻转后得到的t和前半部分“12”进行比较,相等则为回文数。
如何判断翻转数字的位数已经到达原数字位数的一半?我们将原始数字除以 10,然后给反转后的数字乘上 10,所以,当原始数字小于反转后的数字时,就意味着我们已经处理了一半位数的数字。
参数数字x可能是偶数也可能是基数,如果x是偶数,例如“1221”,只要翻转后的“21”等于前半部分“12”,x就是回文数;如果x是基数,例如“12321”,后半部分翻转得到“123”,剩余的前半部分是”12“,但是原始数字中间的这个数字”3“并不影响回文(它总是与自身相等),所以可以直接简单的将后半部分翻转得到“123”进行“123/10=12”的操作即可,然后再与前半部分进行比较。
1 | public boolean isPalindrome(int x) { |
本人菜鸟,有错误请告知,感激不尽!